/*
 * isSubtree.cpp
 *
 *  Created on: Jul 23, 2012
 *      Author: xkq
 */

#include "BSTNode.h"
#include <iostream>

using namespace std;

bool identifySubtree(BSTNode *A, BSTNode *B){
	if(B==NULL)
		return true;
	if(A==NULL)
		return false;

	if(A->data!=B->data)
		return false;

	return identifySubtree(A->left, B->left)&&identifySubtree(A->right, B->right);
}

bool isSubtreeCore(BSTNode *A, BSTNode *B){
	bool result = false;

	if(A->data==B->data)
		result = identifySubtree(A, B);

	if(!result && A->left!=NULL)
		result = isSubtreeCore(A->left, B);
	if(!result && A->right!=NULL)
		result = isSubtreeCore(A->right, B);

	return result;
}

bool isSubtree(BSTNode *A, BSTNode *B){
	if((A!=NULL&&B==NULL)||(A==NULL&&B!=NULL))
		return false;
	if(A==NULL&&B==NULL)
		return true;
	return isSubtreeCore(A, B);
}



